1. Field of the Invention
This invention relates to pattern recognition and more particularly to the detection of minutiae in a binary image of, for example, a fingerprint.
2. Description of the Prior Art
The mushrooming of the various criminal activities in our present-day society has forced the various law enforcement agencies in the United States, as well as in other countries of the world, to encourage the development of automatic fingerprint readers. In response to this need, various types of automatic fingerprint readers have been proposed. Many of the automatic fingerprint readers that have been recently proposed are based upon the detection and location of ridge endings and bifurcations in the fingerprint. These ridge endings and bifurcations, which define the fine features of a fingerprint, are called minutiae. It is believed by many fingerprint experts that such minutiae-based fingerprint readers offer the best means of obtaining a positive identification.
Since the automatic detection of specified minutiae is basically a problem in pattern recognition, it would appear to be a simple matter to provide an automatic system for the detection of such minutiae. However, the recognition of these minutiae is complicated by several factors, such as: (1) the specified minutiae occur at arbitrary orientations; (2) there are variations in ridge breadth and distance between ridge centers; (3) there are various inherent defects in all fingerprints, such as scars, warts, etc.; (4) false ridge endings appear at the boundaries of fingerprints and scars; and (5) the quality of fingerprints varies widely with respect to contrast and clarity. As a result, in almost all cases, the proposed fingerprint reader has either been too complex, too inefficient or inoperative.
For example, it has been proposed to use a large scale computer to control the scan of a fingerprint along some predetermined pattern and to store the resulting complex electrical signal. Subsequently, in order to identify a fingerprint, the fingerprint would have to be scanned and the resultant complex electrical signal compared with those in the memory banks of the computer. Although this approach may well be operative, it has the inherent disadvantage of all mass data-processing systems, and that is the requirement for enormous amounts of complex and costly equipment.
Another suggested approach has been to use holographic techniques whereby two fingerprints may be matched or the location of specified minutiae on fingerprints identified by simultaneously illuminating an unknown fingerprint and a known mask with coherent laser light and determining the locations of a match. However, apparently because of the complexity and the minute detail present in typical fingerprints, it has not been possible to make such a system which operates reliably.
U.S. Pat. No. 3,050,711 to Harmon uses a cathode ray scanner and places transducer elements about a plurality of circles to obtain scans for character recognition.
U.S. Pat. No. 3,859,633 to Ho et al. is directed to a system for detecting minutiae (bifurcations and ridge endings) in a fingerprint pattern. A fingerprint is scanned by a TV camera to produce a corresponding video signal. The video signal is fed into an enhancer circuit which serves to improve the contrast between ridges and valleys of the fingerprint pattern. No specific circuitry is shown for the enhancer circuit and it is also stated that the enhancer circuit comprises no part of the Ho et al. invention. The enhanced video signals are converted to binary signals by a digitizer, which samples the enhanced video signal at a 1 MHz rate, corresponding to a matrix of 350 .times. 262 sampled points representative of the scanned print. The binary signals from the digitizer are fed to parallel continuity logic networks which are monitored to determine the existence and coordinates of minutiae. These continuity logic networks form "conductive paths corresponding to the contrast between ridges and valleys". Each continuity logic network cmprises a source of potential (+V) at the center of a 12 .times. 12 matrix. The +V source functions as a continuity signal. Each matrix point is a logic circuit which functions to generate an output upon the coincidence of a signal from its corresponding storage location in an associated shift register and a signal from one of the four matrix points located adjacent and orthogonal to it.
U.S. Pat. No. 3,611,290 to Luisi is directed to a fingerprint minutiae reading device which automatically detects the location of ridge endings and bifurcations and correspondingly codes them in terms of X, Y and .theta. coordinates. A flying spot scanner is employed to sequentially scan and sample small portions of the fingerprint pattern to derive an electrical analog signal indicative of the pattern at that sampled portion of the fingerprint. The flying spot scanner includes a photomultiplier which produces the electrical analog signal. A quantizer is coupled to the output of the photomultiplier for transforming the electrical analog signal to a digital signal. A plurality of shift registers receives the digital signal output from the quantizer to temporarily store each sampled portion of the fingerprint. This digital representation of the sampled portion of the fingerprint is circulated through the shift registers and transferred to a decision logic circuit. If the decision logic circuit determines that the sampled portion corresponds to minutia (ridge ending or bifurcation) it generates a signal indicating detection of a minutia and correspondingly codes the detected minutia in X, Y and .theta. coordinates.
U.S. Pat. No. 3,699,519 to Campbell discloses an apparatus for scanning live fingerprints with a flying spot scanner and detecting the X, Y location of each minutia (ridge ending or bifurcation) and its .theta. orientation. The logic circuitry for determining the location and orientation of each minutia is the same as that found in U.S. Pat. No. 3,611,290, cited above. The Campbell patent disclosure and claims are directed specifically to an apparatus for determining the characteristics of a fingerprint pattern utilizing a cathode ray spot scanner wherein the scanning pattern at each coordinate location is a plurality of successive polar scans having polar radii of different magnitudes for scanning the plurality of portions at each coordinate location.
U.S. Pat. No. 3,537,070 to Malek discloses a scanner which is adapted to scan succeeding portions of a pattern such as a fingerprint. During each scan of the (fingerprint) pattern, the distance between adjacent segments (ridges) of the (fingerprint) pattern is monitored and a signal generated when this distance is either greater than normal by a predetermined factor or drops below a predetermined threshold. A determination is similarly made as to the width of each segment (ridge) and a signal generated when the width of a segment is greater than normal by a predetermined factor or when it drops below a predetermined threshold. The signals that are derived are applied to a circuit which analyzes signals from several succeeding scans and recognizes various predetermined characteristics (ridges) of the (fingerprint) pattern.
None of the above-described systems teaches or suggests an apparatus which comprises: a first circuit for enhancing two-dimensional binary data with various pore-fill, and line-thin operations; a second circuit responsive to the enhanced binary data for detecting minutiae and providing the X and Y coordinates of the detected minutiae by processing predetermined minutiae patterns detected in a first preselected window of the second circuit; and a third circuit responsive to the enhanced binary data for providing the orientation angles of the detected minutiae by processing line patterns detected in a second preselected window.